package _动态规划系列;

/**
 * @Author: 吕庆龙
 * @Date: 2020/8/21 22:08
 * <p>
 * 功能描述:
 */
public class _1262 {

    public static void main(String[] args) {
        _1262 test = new _1262();
        int[] nums = {3,6,5,1,8};
        test.maxSumDivThree(nums);
    }

    /**
     * https://leetcode-cn.com/problems/greatest-sum-divisible-by-three/solution/dong-tai-gui-hua-by-loveyi-bao-bei/
     *
     * 最优子结构：将状态存在dp数组中，dp[i]存储S % 3 = i 中的S， 其中S表示当前选择的数字累加和。
     * nums[i] %3 = 2:
     * dp[0]=max(dp[0],dp[1]+nms[i]);
     * dp[1]=max(dp[1],dp[2]+nms[i]);
     * dp[2]=max(dp[2],dp[0]+nms[i]);
     *
     * 1、dp[0]和dp[1]和dp[2]都需要维持它的状态,并且更新最大值(因为要求最大值)
     * 2、那么当nums[i]%3 = 2时:
     *   2.1、dp[0]需要dp[1]【也就是余数为1的这个状态】+ nums[i]【也就是知道nums[i]%3 = 2】
     *      此时余数1+余数2  刚好可以维持dp[0]余数为0的状态，同时还要更新下最大值
     *   2.2 dp[1]  需要dp[2]【余数为2】+ nums[i]才能维持dp[1]【余数为1的状态】
     *
     *
     *
     */
    public int maxSumDivThree(int[] nums) {
        int[] dp = {0, Integer.MIN_VALUE, Integer.MIN_VALUE};
        for (int n : nums) {
            int[] next = {0, 0, 0}; //相当于保存前一个数的dp
            int mod = n % 3;
            for (int i = 0; i < 3; i++) {
                int temp = 3 + i - mod;
                next[i] = Math.max(dp[i], dp[temp % 3] + n);
            }
            dp = next;
        }

        return dp[0];
    }
}
